package com.leetcode.根据情景进行分类;

/**
 * @author: xiaomi
 * @date: 2020/12/24
 * @description: 剑指 Offer 10- II. 青蛙跳台阶问题
 * https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/
 */
public class A_剑指_Offer_10_II_青蛙跳台阶问题 {

    /**
     * 分析：
     * 这是天生的递归，好吧感觉又不是了！
     * n:  0,1,2,3
     * res:1,1,2,
     * --
     * 这个应该是个排列组合，主要看 2 的位置
     * --
     * 好吧这个居然还是递归，类似斐波那契
     * --如果直接用递归，由于存在大量的重复计算，于是会超出时间限制！
     * --
     * 分析：首先这个题目得先理解关键：
     * 最后一步，可以为 n-1,n-2,那么 f(n)=f(n-1)+f(n-2)
     * 理解了这个以后就可以，真正从编程上来解决问题！
     *
     * @param n
     * @return
     */
    public int numWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return numWays(n - 1) + numWays(n - 2);
    }

    /**
     * 这个就是迭代的优化版本！时间复杂度大大缩小
     * @param n
     * @return
     */
    public int numWays2(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        int count = 0;
        int n1 = 1;//n == 0
        int n2 = 1;//n == 1
        int temp = 0;
        for (int i = 2; i <= n; i++) {
            temp = n1;
            n1 = n1 + n2;
            n2 = temp;
            if(n1>1000000007){
                n1=n1 % 1000000007;
            }
        }
        return n1 % 1000000007;
    }

    public static void main(String[] args) {

    }
}
